package 力扣_简单题;

/*小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。

小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ccw6C7
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class 黑白方格画 {
    public int paintingPlan(int n, int k) {
//        当n=1
        if(k==n*n)
            return 1;
        int ans = 0;
        for(int a=0; a<n; a++) {
            for (int b = 0; b < n; b++) {
                int sum = a * n + b * n - a * b;//计算黑格子总的多少个，a*b时重复的，要减去
                if (sum == k) {
                    int x = combination(n, a);
                    int y = combination(n, b);
                    ans += x * y;
                }
            }
        }
        return ans;
    }
//    进行排列组合计算,对公式进行化简
    int combination (int n,int a){
        int result = 1;
        for(int i=n; i>a; --i)
            result *= i;
        for(int i=n-a; i>0; --i){
            result /= i;
        }
        return result;
    }
}
